//给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重
//复的三元组。 
//
// 注意：答案中不可以包含重复的三元组。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [-1,0,1,2,-1,-4]
//输出：[[-1,-1,2],[-1,0,1]]
// 
//
// 示例 2： 
//
// 
//输入：nums = []
//输出：[]
// 
//
// 示例 3： 
//
// 
//输入：nums = [0]
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// 0 <= nums.length <= 3000 
// -105 <= nums[i] <= 105 
// 
// Related Topics 数组 双指针 
// 👍 2935 👎 0

package com.simon.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ThreeSum_15 {
    public static void main(String[] args) {
        Solution solution = new ThreeSum_15().new Solution();
//        int[]    nums = new int[]{-1,0,1,2,-1,-4};
//        int[]    nums = new int[]{0,0,0};
        int[]    nums = new int[]{-1,0,1,2,-1,-4,-2,-3,3,0,4};
//        int[]    nums = new int[]{0,0,0,0,0};
        List<List<Integer>> lists = solution.threeSum(nums);
        System.out.println(lists);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            Arrays.sort(nums);          //后续后解决重复问题
            List<List<Integer>> result = new ArrayList<>();
            for (int i = 0; i < nums.length - 2; i++) {
                if (i > 0 && nums[i] == nums[i - 1]) {      //前后相等，直接跳过
                    continue;
                }
                int k = nums.length-1;
                for (int j = i + 1; j < nums.length - 1; j++) {
                    if (j > i + 1 && nums[j] == nums[j - 1]) {  //前后相等，直接跳过
                        continue;
                    }
                    /**
                     * 因为数组已经经过从小到达排序，这里只需要判断是否>0，>0才需要移动第三个指针，否则这个循环已经没有=0的可能;
                     *                       如果这里判断!=0，怎将会提前把第三指针移动，导致丢失其他正确的可能性
                     */
                    while (j < k && nums[i] + nums[j] + nums[k] > 0) {
                        k--;
                    }
                    if(j==k) {
                        break;
                    }
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        //满足条件
//                        System.out.println(String.format("%d,%d,%d", nums[i], nums[j], nums[k]));
                        List<Integer> match = Arrays.asList(nums[i], nums[j], nums[k]);
                        result.add(match);
                    }
                }
            }
            return result;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}